home *** CD-ROM | disk | FTP | other *** search
/ C/C++ Users Group Library 1996 July / C-C++ Users Group Library July 1996.iso / vol_200 / 241_01 / verify.ci < prev    next >
Text File  |  1987-08-29  |  7KB  |  258 lines
  1. /*
  2. HEADER:         CUG241;
  3. TITLE:          Inference Engine for Expert System;
  4. DATE:           12/30/85;
  5. VERSION:
  6. DESCRIPTION:   "Source code for inference engine for an Expert System.";
  7. KEYWORDS:       Artificial Intelligence, expert systems, inference engine;
  8. SYSTEM:         MS-DOS or UNIX System V;
  9. FILENAME:       VERIFY.C;
  10. WARNINGS:      "User-supported, non-commercial"
  11. AUTHORS:        George Hageman; 
  12. COMPILERS:      Microsoft C V3.00 or UNIX System V Portable C Compiler;
  13. REFERENCES:     ;
  14. ENDREF
  15. */
  16.  
  17. /*****************************************************************
  18. **                                **
  19. **      Inference -- (C) Copyright 1985 George Hageman    **
  20. **                                **
  21. **        user-supported software:                **
  22. **                                **
  23. **            George Hageman                **
  24. **            P.O. Box 11234                **
  25. **            Boulder, Colorado 80302            **
  26. **                                **
  27. *****************************************************************/
  28.  
  29. /********************************************************
  30. **
  31. **    verify(consequent)
  32. **
  33. **    finds the truth about the consequent -- returns
  34. **    TRUE if consequent is proved (all antecedents are TRUE)
  35. **    FALSE if any of the antecedents are FALSE
  36. **
  37. ********************************************************/
  38.  
  39. #include <stdio.h>
  40. #include "expert.h"
  41. #include "inference.h"
  42.  
  43. int    verify(cnsquent) 
  44.     int    cnsquent ;
  45.  
  46. {
  47. int     i,j,k,m,n ;
  48. int    antecedent[MAX_ANTECEDENTS] ;
  49. int    consequent[MAX_ANTECEDENTS] ;
  50. int    p_value ;            /* predicate value */
  51.  
  52. #ifdef DEBUG
  53.     int di ;
  54.     for(di=0;di<numTrue;di++)
  55.         printf("\nDEBUG-verify knownTrueFact = %d",knownTrue[di]) ;
  56.     for(di=0;di<numFalse;di++)
  57.         printf("\nDEBUG-verify knownFalseFact = %d",knownFalse[di]) ;
  58.  
  59. #endif
  60.  
  61. /*
  62. **
  63. **    get all of the antecedents for the consequent
  64. **
  65. **    First locate the antecedents -- should be directly in front
  66. **    of the consequent, delimited by a consequent with a flag of zero
  67. */
  68.  
  69. #ifdef DEBUG
  70.     printf("\nDEBUG -- verify consequent = %d",cnsquent ) ;
  71. #endif
  72.  
  73. j = 0 ;
  74.  
  75. for(i=cnsquent; i>=0 ; i--)
  76.     {
  77.     if(ruleBuff[i].flag == 0 )
  78.         break ;
  79.     }
  80.  
  81. if(i == -1)
  82.     {
  83.     printf("\n Bad Consequent, has no antecedents! returning TRUE value \n ") ;
  84.     return(TRUE);
  85.     }
  86.  
  87. for(i = i-1 ;i>=0; i--)
  88.     {
  89.     if(ruleBuff[i].flag != 0)
  90.         antecedent[j++]=i ;
  91.     else
  92.         break ;
  93.     }
  94.  
  95. if(j==0)
  96.     {
  97.     printf("\n Bad Consequent, has no antecedents! returning TRUE value \n ") ;
  98.     return(TRUE);
  99.     }
  100.     
  101. #ifdef DEBUG
  102.     printf("\nDEBUG -- verify antecedents = ") ;
  103.     for(di=0; di < j; di++)
  104.         printf("\n     %d -- %d",di,antecedent[di]) ;
  105. #endif
  106.  
  107. /*
  108. **    at this point we should have some antecedents in the antecedent
  109. **    stack so now lets see if each can be proved, and if there are
  110. **    any consequents which will need verification.
  111. */
  112.  
  113. /*
  114. **    main verificaiton loop:
  115. */
  116.  
  117. for(i=j-1 ; i >= 0 ; i--) /* for all of the antecedents in our stack */ 
  118.     {
  119.  
  120. /*
  121. **    determine if the antecedent is itself a consequent
  122. **    
  123. **    compare value of the string pointer of the antecedent needs to
  124. **    be compaired with the value of the string pointer of all of the
  125. **    consequents, if there is a match then the antecedent is a consequent
  126. **
  127. **    There may be more
  128. **    than one consequent and this is handled below since all of these
  129. **    must be false before we give up hope that one will be verified--
  130. **    REMEMBER -- consequents are not remembered FALSE they can only be
  131. **    remembered when they are true -- FALSEness for a consequent merely
  132. **    means that this particular rule did not verify it , some other one
  133. **    might.
  134. **
  135. */
  136.  
  137.     for(k=0; k< numHypot; k++ )
  138.         if(ruleBuff[hypStack[k]].string == ruleBuff[antecedent[i]].string)
  139.             break ;
  140.  
  141.     if(k != numHypot)  /* we have an antecedent which is a consequent */
  142.         {
  143.  
  144. #ifdef DEBUG
  145.     printf("\nDEBUG -- verify antecedent %d is consequent %d",i, antecedent[i] ) ;
  146. #endif
  147.  
  148. /*
  149. **    What we have is an antecedent which is a consequent of another
  150. **    rule or rules.  What is needed then is to place each of these consequents
  151. **    into a stack and prove them one at a time.  We will return truth
  152. **    if any of these are proven true and return false only when all of
  153. **    them are false.   We can use veriry recursively in this case to
  154. **    verify each one.
  155. **
  156. **    get all consequents matching hypStack[k].string into a stack
  157. **    look for truth of any consequent.
  158. **    if consequent is true (according to flag) return true.
  159. **    if all consequents are false then return false.
  160. */
  161.         n = 0 ;
  162.         for( m = 0 ; m < numHypot ; m++)
  163.             {
  164.             if(ruleBuff[antecedent[i]].string == ruleBuff[hypStack[m]].string)
  165.                 {
  166. #ifdef DEBUG
  167.                 printf("\nDEBUG--consequent stack(%d) = %d",n,hypStack[m]) ;
  168. #endif
  169.                 consequent[n++] = hypStack[m] ;
  170.                 }
  171.             }
  172. /*
  173. **    verify each consequent
  174. */
  175.  
  176.         p_value = FALSE ;
  177.         for(m = 0 ; m < n ; m++)        
  178.             {
  179.  
  180. #ifdef DEBUG
  181.     printf("\nDEBUG -- verify(2) consequent = %d",consequent[m] ) ;
  182. #endif
  183.             if( verify(consequent[m]) == TRUE )
  184.                 {
  185.                 p_value = TRUE ;
  186.                 if(known(consequent[m],knownTrue,numTrue) == FALSE)
  187.                     {
  188.                     printf("\nI infer that : %s\n",&strBuff[ruleBuff[consequent[m]].string]) ;
  189.                     knownTrue[numTrue++]=ruleBuff[consequent[m]].string ;
  190.                     }
  191.                 if(remAnte(antecedent[i]) == TRUE)
  192.                     {
  193.                     break ;
  194.                     }
  195.                 else
  196.                     {
  197.                     return(FALSE) ;
  198.                     }
  199.                 }
  200.             }
  201.         if(p_value == FALSE) /* all of the consequents were not proved */
  202.             {
  203.             switch(ruleBuff[antecedent[i]].flag)
  204.                 {
  205.                 case STRING_FALSE :
  206.                 case ROUTINE_FALSE :
  207.                     continue ;
  208.                 case STRING_TRUE :
  209.                 case STRING_TRUE_HYP :
  210.                 case ROUTINE_TRUE :
  211.                 case ROUTINE_TRUE_HYP :
  212.                     return(FALSE) ;
  213.                 }
  214.             }
  215.         else            /* at least one was known */
  216.             {
  217.             switch(ruleBuff[antecedent[i]].flag)
  218.                 {
  219.                 case STRING_TRUE :
  220.                 case STRING_TRUE_HYP :
  221.                 case ROUTINE_TRUE:
  222.                 case ROUTINE_TRUE_HYP:
  223.                     continue ;
  224.                 case STRING_FALSE :
  225.                 case ROUTINE_FALSE :
  226.                     return(FALSE) ;
  227.                 }
  228.             }
  229.         }
  230.         
  231.     else    /* we have a plane old string or routine antecedent */
  232.         
  233.         {
  234.         
  235.         if(weKnow(antecedent[i],&p_value) == TRUE)
  236.             {
  237.             if(p_value == TRUE)
  238.                 continue ;
  239.             else
  240.                 return(FALSE) ;
  241.             }
  242. /*
  243. **    Things arent known and are simple consequents so prove them
  244. **    either by asking the user or by running the routine
  245. */
  246.         if(verifyTruth(antecedent[i]) == TRUE)
  247.             continue ;
  248.         else
  249.             return(FALSE) ;
  250.         }
  251.     }
  252. /*
  253. **    Everything was TRUE in the big and statement so return it
  254. */
  255. return(TRUE) ;
  256. }
  257.  
  258.